package com.gaogzhen.datastructure.graph.directed;

import com.gaogzhen.datastructure.graph.undirected.Entry;
import com.gaogzhen.datastructure.stack.Stack;
import edu.princeton.cs.algs4.*;

import java.util.Iterator;

/**
 *  基于深度优先的顶点排序
 * @author gaogzhen
 */
public class DepthFirstOrder {

    /**
     * 顶点已访问标记
     */
    private boolean[] marked;

    /**
     * 基于深度优先的顶点前序排列索引
     */
    private int[] pre;

    /**
     * 基于深度优先的顶点后序排序索引
     */
    private int[] post;

    /**
     * 基于深度优先的顶点前序排列
     */
    private Queue<Integer> preOrder;

    /**
     * 基于深度优先的后序排列
     */
    private Queue<Integer> postOrder;

    /**
     * 当前前序顶点计数
     */
    private int preCounter;

    /**
     * 当前后序顶点计数
     */
    private int postCounter;

    /**
     * 深度优先的顶点排序
     * @param digraph 有向图
     */
    public DepthFirstOrder(Digraph digraph) {
        pre    = new int[digraph.V()];
        post   = new int[digraph.V()];
        postOrder = new Queue<Integer>();
        preOrder  = new Queue<Integer>();
        marked    = new boolean[digraph.V()];
        for (int v = 0; v < digraph.V(); v++) {
            if (!marked[v]) {
                dfs(digraph, v);
            }
        }

        assert check();
    }

    /**
     * 有向图的深度优先顶点排序
     * @param digraph   有向图digraph
     * @param v 起点
     */
    private void dfs(Digraph digraph, int v) {
        Stack<Entry<Integer, Iterator<Integer>>> path = new Stack<>();
        // marked[v] = true;
        if (!marked[v]) {
            // 键值对起点-起点对应邻接表迭代器压入栈中
            marked[v] = true;
            pre[v] = preCounter++;
            preOrder.enqueue(v);
            Iterable<Integer> iterable = digraph.adj(v);
            Iterator<Integer> it;
            if (iterable != null && (it = iterable.iterator()) != null){
                path.push(new Entry<>(v, it));
            }
        }
        // 保证深度优先跳转标记
        nextLevel:
        while (!path.isEmpty()) {
            Entry<Integer, Iterator<Integer>> entry = path.pop();
            int x;
            Iterator<Integer> it = entry.getValue();
            Integer f = entry.getKey();
            while (it.hasNext()) {
                // 当前顶点对应的邻接表迭代器还有元素，获取下一个元素
                x = it.next();
                if (!marked[x]) {
                    // 顶点未被标记，标记顶点且标记路径x->f
                    // f是x所在邻接表对应的顶点
                    marked[x] = true;
                    pre[x] = preCounter++;
                    preOrder.enqueue(x);
                    // if (it.hasNext()) {
                        // 邻接表迭代器还有元素，重新压入栈
                        path.push(entry);
                    // }
                    // 按照深度优先原则，把新标记顶点对应的键值对压入栈中，在下次循环时优先访问
                    Iterable<Integer> iterable = digraph.adj(x);
                    if (iterable != null && (it = iterable.iterator()) != null){
                        path.push(new Entry<>(x, it));
                    }
                    // 保证深度优先：下一层有未访问结点，优先访问下层结点
                    continue nextLevel;
                }
            }

            // 顶点f对应的邻接表访问完毕，后序排列开始记录
            postOrder.enqueue(f);
            post[f] = postCounter++;
        }
    }

    /**
     * 返回指定顶点v在前序排列中的索引
     * @param  v 指定顶点v
     * @return 指定顶点v在前序排列中的索引
     * @throws IllegalArgumentException unless {@code 0 <= v < V}
     */
    public int pre(int v) {
        validateVertex(v);
        return pre[v];
    }

    /**
     * 返回顶点v在后序排列中的索引
     * @param  v 顶点v
     * @return 顶点v在后序排列中的索引
     * @throws IllegalArgumentException unless {@code 0 <= v < V}
     */
    public int post(int v) {
        validateVertex(v);
        return post[v];
    }

    /**
     * 返回顶点的后序排列
     */
    public Iterable<Integer> post() {
        return postOrder;
    }

    /**
     * 返回顶点的前序排列
     */
    public Iterable<Integer> pre() {
        return preOrder;
    }

    /**
     * 返回顶点的逆后序排列
     */
    public Iterable<Integer> reversePost() {
        Stack<Integer> reverse = new Stack<Integer>();
        for (int v : postOrder) {
            reverse.push(v);
        }
        return reverse;
    }


    /**
     * 校验前序和后序排列结果是否和pre(v)与post(v)相等
     * @return {@code true}结果一致;{@code false}有一个不相等
     */
    private boolean check() {

        // check that post(v) is consistent with post()
        int r = 0;
        for (int v : post()) {
            if (post(v) != r) {
                StdOut.println("post(v) and post() inconsistent");
                return false;
            }
            r++;
        }

        // check that pre(v) is consistent with pre()
        r = 0;
        for (int v : pre()) {
            if (pre(v) != r) {
                StdOut.println("pre(v) and pre() inconsistent");
                return false;
            }
            r++;
        }

        return true;
    }

    /**
     * 校验顶点v
     * @param v 顶点v
     */
    private void validateVertex(int v) {
        int V = marked.length;
        if (v < 0 || v >= V) {
            throw new IllegalArgumentException("vertex " + v + " is not between 0 and " + (V-1));
        }
    }

}